The present invention generally relates to methods of segmenting characters of document images, and more particularly to a method of segmenting characters of a document image which may include a skew.
Generally, an optical character recognition apparatus or the like obtains horizontal projections of an input document image (binary image) in a direction of lines of characters and vertical projections of the input document image in a direction perpendicular to the direction of the lines. A line segmentation is made by discriminating each line and each space between the lines from the horizontal projections, and a character segmentation is made by determining a range of the character segmentation from the vertical projections.
The horizontal and vertical projections are sometimes also referred to as peripheral distributions. Usually, the projection corresponds to a number of black picture elements (or white picture elements in a special case) within a certain region. The number of black picture elements in one data line within the certain region is counted, and this counted value is called the horizontal projection. The data line is made up of horizontally arranged picture elements. The horizontal projection is obtained for each of the data lines within the certain region, and the obtained horizontal projections are referred to as the "horizontal projections of the certain region" or simply "horizontal projections". The vertical projection is similar to the horizontal projection except that the black picture elements are counted in a vertical direction which is perpendicular to the horizontal direction.
But when the document image includes a skew such as a case where the lines of characters are greatly inclined in the document image, the horizontal projections of two successive lines become continuous when the horizontal projections are obtained with respect to the full width of the document image, and it becomes impossible to make a normal line segmentation. As a result, it becomes impossible to make a normal character segmentation.
In order to cope with the skew included in the document image, there is a known method which divides the document image in the direction of the lines into equal regions. The line segmentation is made by discriminating each line or each space between the lines from the horizontal projections within the range of the divided region for each of the divided regions. The character segmentation is made by determining the range of the character segmentation from the vertical projections of the segmented lines.
However, this known method suffers problems in that it is difficult to make the segmentation of a character which is located at a boundary between two divided regions, a special and troublesome process is required to make the segmentation of such a character, and a processing speed as a whole becomes poor.
FIG. 1 shows a case where a character "y" is located at a boundary between two divided regions I and II. It is assumed for the sake of convenience that there does not exist a character which has a height greater than that of a character "n" in the divided region I and there does not exist a character which has a height greater than that of the character "y" in the divided region II. In this case, the start and end positions of the line in the divided regions I and II are determined as shown from the respective horizontal projections.
Basically, the character segmentation is made by respectively setting the start and end positions of the line in each divided region as the top and bottom ends of the range of the character segmentation within the divided region. However, in the case of the character "y" which is located at the boundary between the two divided regions I and II and spans the two divided regions I and II, the start and end positions of the line differ between the divided region I in which a left portion of the character "y" belongs and the divided region II in which a right portion of the character "y" belongs as may be seen from FIG. 1. Moreover, even the line end position of the line which is within the divided region II and has the greater line width is still above the bottom end of the character "y" at the boundary. Accordingly, when the left portion of the character "y" is segmented by taking the start and end positions of the line within the divided region I as the top and bottom ends of the range of the character segmentation and the right portion of the character "y" is segmented by taking the start and end positions of the line within the divided region II as the top and bottom ends of the range of the character segmentation, a lower portion of the character "y" greatly drops out. On the other hand, even when the start and end positions of the line within the divided region II which are respectively higher and lower than the start and end positions of the line within the divided region I are taken as the top and bottom ends of the range of the character segmentation, the lower portion of the character "y" still drops out.
Therefore, when the character is located at the boundary between two divided regions and spans the two divided regions, it is difficult to unitarily determine the top and bottom ends of the range of the character segmentation. Furthermore, it requires a complex process to normally make the segmentation of the character located at the boundary.
On the other hand, as a method of processing the skew, there is a known method in which the extraction of the vertical projections is carried out simultaneously or in parallel to the line segmentation. But conventionally, the extraction of the vertical projections is carried out only with respect to a present line which is the subject of the segmentation. For this reason, a re-processing of the image data and a back-tracking are needed to extract the vertical projections of a next line, and there is a problem in that the processing efficiency is poor.